package Sort;

import java.util.Arrays;

/**
 * @Classname 二分法
 * @Description TODO
 * @Date 2023/2/18 9:24
 * @Created by xjl
 */
public class 二分法 {

    /**
     * @description:二分查找算法使用有序数组 局部有序数组也可以使用
     * @author: zhuangxiaoyan
     * @date: 2023/10/12 18:04
     * @param: [Array, target]
     * @return: int
     **/
    private static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) >>> 1;
            int midValue = array[mid];
            if (midValue < target) {
                left = mid + 1;
            } else if (midValue > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -(left + 1);
    }

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        // 有序数组才能使用二分法
        System.out.println(binarySearch(array, 38));
    }
}